"""
希尔排序：
    - 希尔排序是一种分组插入排序算法
    - 首先取一个整数d1=n/2, 将元素分为d1个组, 每组相邻的元素之间的距离为d1, 在各组内进行直接插入排序
    - 取第二个整数d2=d1/2, 重复上述分组排序过程, 直到di=1, 即所有元素在同一组内进行直接 插入排序
    - 希尔排序每趟并不使某些元素有序；最后一趟排序使得所有数据有序
时间复杂度：最坏情况是O(n**2),
"""
from SortingAlgorithm.cal_time.cal_time import cal_time


def insert_sort_gap(li, gap):
    for i in range(gap, len(li)):  # i 表示摸到的牌的下标  有序区【所以至少有一张】
        tmp = li[gap]
        j = i - gap  # j指的是手里(摸到的牌的左边间隔为gap的牌)的牌的下标
        while j >= 0 and li[j] > tmp:
            li[j+gap] = li[j]
            j -= gap
        li[j+gap] = tmp


@cal_time(name="希尔排序时间")
def shell_sort(li):
    d = len(li) // 2
    while d >= 1:
        insert_sort_gap(li, d)
        d //= 2


if __name__ == "__main__":
    li = list(range(10000))
    import random
    random.shuffle(li)
    shell_sort(li)

